#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn = 2e5 + 10;
const int p = 1e9 + 7;

int dp[maxn][20][2][2]; // pos zero 不同数字的个数 
int digit[maxn];
int cnt;

string s;
int K;

// 统计 1 的个数
int count (int x) {
	int res=0;
	while(x){
		res++;
		x=(x&(x-1));
	}
	return res;
}


int dfs(int pos, int limit, int zero, int prev){
	int x=count(prev);
	if (pos==0) {
		return x==K;
	}
	
	if (x>K) {
		return 0;
	}
	
	if (dp[pos][x][limit][zero] != -1  ) { 
		return dp[pos][x][limit][zero];
	}
	
	int up = limit?digit[pos]:15;
	int res=0;
	for (int i=0;i<=up;i++) {
		res = (res+dfs(pos-1, limit&&(i==up), zero&&(i==0), (zero&&!i)?prev:prev|(1<<i)))%p;
	}
	
	dp[pos][x][limit][zero]=res;

	
	return res;
}



void solve(){
	cin>>s;
	cin>>K;
	memset(dp, -1, sizeof(dp));
	reverse(s.begin(), s.end());
	for (int i=1;i<=s.length();i++) {
		if (isdigit(s[i-1])) {
			// 0-9
			digit[i] = s[i-1]-'0';
		} else {
			// a-e
			digit[i] = s[i-1]-'A'+10;
		}
	}
	
	cout << dfs(s.length(), 1, 1, 0) <<'\n';
}

signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}
